package com.hqq.leetcode.tree;

import com.hqq.exercise.tree.TreeNode;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * LevelOrder 二叉树的层序遍历
 * Description:
 * Given a binary tree, return the level order traversal of its nodes' values.
 * (ie, from left to right, level by level).
 * Input:
 * -----3
 * ----/ \
 * ---9  20
 * -----/  \
 * ----15   7
 * <p>
 * Output:
 * [
 * [3],
 * [9,20],
 * [15,7]
 * ]
 * Created by heqianqian on 2017/9/13.
 */
public class LevelOrder {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode lChild = new TreeNode(9);
        TreeNode rChild = new TreeNode(20);
        lChild.left = new TreeNode(10);
        lChild.right = new TreeNode(19);
        rChild.left = new TreeNode(15);
        rChild.right = new TreeNode(7);
        root.left = lChild;
        root.right = rChild;

        LevelOrder lo = new LevelOrder();
        List<List<Integer>> lists = lo.levelOrder(root);
        System.out.println(lists);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        return levelOrderRecursion(root, 0, lists);
        //return levelOrderTraversal(root);
    }

    public List<List<Integer>> levelOrderRecursion(TreeNode root, int level, List<List<Integer>> lists) {
        if (root == null) {
            return null;
        }
        if (level == lists.size()) {
            lists.add(new ArrayList<>());
        }
        lists.get(level).add(root.val);
        if (root.left != null) {
            levelOrderRecursion(root.left, level + 1, lists);
        }
        if (root.right != null) {
            levelOrderRecursion(root.right, level + 1, lists);
        }
        return lists;
    }

    public List<List<Integer>> levelOrderTraversal(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }
}
